Actualmente estoy escribiendo un analizador básico para un sabor XML. Como ejercicio, estoy implementando un analizador basado en tablas LL. Este es mi ejemplo de gramática BNF: % cadena de datos del nombre del token %% / * LL (1) * / doc: elem elem: "<" etiqueta_abierta open_tag: nombre attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" open_tag elem_or_data | datos elem_or_data | / * épsilon * / ; attr: name ":" string attr | / * épsilon * / ; ¿Es esta gramática correcta? Cada literal terminal está entre comillas. Los terminales abstractos se especifican mediante% token. Estoy codificando un lexer escrito a mano para convertir mi entrada en una lista de tokens. ¿Cómo tokenizaría los terminales abstractos?
2021-03-03 08:12:27
El enfoque clásico sería escribir una expresión regular (u otro reconocedor) para cada terminal posible.
Lo que usted llama terminales "abstractos", que son perfectamente concretos, son en realidad terminales cuyos patrones asociados reconocen más de una posible cadena de entrada. La cadena realmente reconocida (o alguna función calculada de esa cadena) debe pasarse al analizador como el valor semántico del token.
Nominalmente, en cada punto de la cadena de entrada, el tokenizador ejecutará todos los reconocedores y elegirá el que tenga la coincidencia más larga. (Esta es la llamada regla de "masticación máxima"). Esto normalmente se puede optimizar, especialmente si todos los patrones son expresiones regulares. (F) lex hará esa optimización por usted, por ejemplo.
Una complicación en su caso es que la tokenización de su idioma depende del contexto. En particular, cuando el objetivo es elem_or_data, los únicos tokens posibles son <,